Semisupervised Laplace-Regularized Multimodality Metric Learning.

Distance metric learning, which aims at learning an appropriate metric from data automatically, plays a crucial role in the fields of pattern recognition and information retrieval. A tremendous amount of work has been devoted to metric learning in recent years, but much of the work is basically designed for training a linear and global metric with labeled samples. When data are represented with multimodal and high-dimensional features and only limited supervision information is available, these approaches are inevitably confronted with a series of critical problems: 1) naive concatenation of feature vectors can cause the curse of dimensionality in learning metrics and 2) ignorance of utilizing massive unlabeled data may lead to overfitting. To mitigate this deficiency, we develop a semisupervised Laplace-regularized multimodal metric-learning method in this work, which explores a joint formulation of multiple metrics as well as weights for learning appropriate distances: 1) it learns a global optimal distance metric on each feature space and 2) it searches the optimal combination weights of multiple features. Experimental results demonstrate both the effectiveness and efficiency of our method on retrieval and classification tasks.

Quantitative thresholds based decision support approach for the home health care scheduling and routing problem.

In the domain of Home Health Care (HHC), precise decisions regarding patient's selection, staffing level, and scheduling of health care staff have a significant impact on the efficiency and effectiveness of the HHC system. However, decentralized planning, the absence of well defined decision rules, delayed decisions and lack of interactive tools typically lead towards low satisfaction level among all the stakeholders of the HHC system. In order to address these issues, we propose an integrated three phase decision support methodology for the HHC system. More specifically, the proposed methodology exploits the structure of the HHC problem and logistic regression based approaches to identify the decision rules for patient acceptance, staff hiring, and staff utilization. In the first phase, a mathematical model is constructed for the HHC scheduling and routing problem using Mixed-Integer Linear Programming (MILP). The mathematical model is solved with the MILP solver CPLEX and a Variable Neighbourhood Search (VNS) based method is used to find the heuristic solution for the HHC problem. The model considers the planning concerns related to compatibility, time restrictions, distance, and cost. In the second phase, Bender's method and Receiver Operating Characteristic (ROC) curves are implemented to identify the thresholds based on the CPLEX and VNS solution. While the third phase creates a fresh solution for the HHC problem with a new data set and validates the thresholds predicted in the second phase. The effectiveness of these thresholds is evaluated by utilizing performance measures of the widely-used confusion matrix. The evaluation of the thresholds shows that the ROC curves based thresholds of the first two parameters achieved 67% to 71% accuracy against the two considered solution methods. While the Bender's method based thresholds for the same parameters attained more than 70% accuracy in cases where probability value is small (p ≤ 0.5). The promising results indicate that the proposed methodology is applicable to define the decision rules for the HHC problem and beneficial to all the concerned stakeholders in making relevant decisions.

A Deterministic Annealing Neural Network Algorithm for the Minimum Concave Cost Transportation Problem.

In this article, a deterministic annealing neural network algorithm is proposed to solve the minimum concave cost transportation problem. Specifically, the algorithm is derived from two neural network models and Lagrange-barrier functions. The Lagrange function is used to handle linear equality constraints, and the barrier function is used to force the solution to move to the global or near-global optimal solution. In both neural network models, two descent directions are constructed, and an iterative procedure for the optimization of the neural network is proposed. As a result, two corresponding Lyapunov functions are naturally obtained from these two descent directions. Furthermore, the proposed neural network models are proved to be completely stable and converge to the stable equilibrium state, therefore, the proposed algorithm converges. At last, the computer simulations on several test problems are made, and the results indicate that the proposed algorithm always generates global or near-global optimal solutions.

An approximation algorithm for graph partitioning via deterministic annealing neural network.

Graph partitioning, a classical NP-hard combinatorial optimization problem, is widely applied to industrial or management problems. In this study, an approximated solution of the graph partitioning problem is obtained by using a deterministic annealing neural network algorithm. The algorithm is a continuation method that attempts to obtain a high-quality solution by following a path of minimum points of a barrier problem as the barrier parameter is reduced from a sufficiently large positive number to 0. With the barrier parameter assumed to be any positive number, one minimum solution of the barrier problem can be found by the algorithm in a feasible descent direction. With a globally convergent iterative procedure, the feasible descent direction could be obtained by renewing Lagrange multipliers red. A distinctive feature of it is that the upper and lower bounds on the variables will be automatically satisfied on the condition that the step length is a value from 0 to 1. Four well-known algorithms are compared with the proposed one on 100 test samples. Simulation results show effectiveness of the proposed algorithm.

Calibrating Classification Probabilities with Shape-Restricted Polynomial Regression.

In many real-world classification problems, accurate prediction of membership probabilities is critical for further decision making. The probability calibration problem studies how to map scores obtained from one classification algorithm to membership probabilities. The requirement of non-decreasingness for this mapping involves an infinite number of inequality constraints, which makes its estimation computationally intractable. For the sake of this difficulty, existing methods failed to achieve four desiderata of probability calibration: universal flexibility, non-decreasingness, continuousness and computational tractability. This paper proposes a method with shape-restricted polynomial regression, which satisfies all four desiderata. In the method, the calibrating function is approximated with monotone polynomials, and the continuously-constrained requirement of monotonicity is equivalent to some semidefinite constraints. Thus, the calibration problem can be solved with tractable semidefinite programs. This estimator is both strongly and weakly universally consistent under a trivial condition. Experimental results on both artificial and real data sets clearly show that the method can greatly improve calibrating performance in terms of reliability-curve related measures.

Weighted Graph Embedding-Based Metric Learning for Kinship Verification.

Given a group photograph, it is interesting and useful to judge whether the characters in it share specific kinship relation, such as father-daughter, father-son, mother-daughter, or mother-son. Recently, facial image-based kinship verification has attracted wide attention in computer vision. Some metric learning algorithms have been developed for improving kinship verification. However, most of the existing algorithms ignore fusing multiple feature representations and utilizing kernel techniques. In this paper, we develop a novel weighted graph embedding-based metric learning (WGEML) framework for kinship verification. Inspired by the fact that family members usually show high similarity in facial features like eyes, noses, and mouths, despite their diversity, we jointly learn multiple metrics by constructing an intrinsic graph and two penalty graphs to characterize the intraclass compactness and interclass separability for each feature representation, respectively, so that both the consistency and complementarity among multiple features can be fully exploited. Meanwhile, combination weights are determined through a weighted graph embedding framework. Furthermore, we present a kernelized version of WGEML to tackle nonlinear problems. Experimental results demonstrate both the effectiveness and efficiency of our proposed methods.

Space Structure and Clustering of Categorical Data.

Learning from categorical data plays a fundamental role in such areas as pattern recognition, machine learning, data mining, and knowledge discovery. To effectively discover the group structure inherent in a set of categorical objects, many categorical clustering algorithms have been developed in the literature, among which k -modes-type algorithms are very representative because of their good performance. Nevertheless, there is still much room for improving their clustering performance in comparison with the clustering algorithms for the numeric data. This may arise from the fact that the categorical data lack a clear space structure as that of the numeric data. To address this issue, we propose, in this paper, a novel data-representation scheme for the categorical data, which maps a set of categorical objects into a Euclidean space. Based on the data-representation scheme, a general framework for space structure based categorical clustering algorithms (SBC) is designed. This framework together with the applications of two kinds of dissimilarities leads two versions of the SBC-type algorithms. To verify the performance of the SBC-type algorithms, we employ as references four representative algorithms of the k -modes-type algorithms. Experiments show that the proposed SBC-type algorithms significantly outperform the k -modes-type algorithms.

Robust Novelty Detection via Worst Case CVaR Minimization.

Novelty detection models aim to find the minimum volume set covering a given probability mass. This paper proposes a robust single-class support vector machine (SSVM) for novelty detection, which is mainly based on the worst case conditional value-at-risk minimization. By assuming that every input is subject to an uncertainty with a specified symmetric support, this robust formulation results in a maximization term that is similar to the regularization term in the classical SSVM. When the uncertainty set is l1 -norm, l∞ -norm or box, its training can be reformulated to a linear program; while the uncertainty set is l2 -norm or ellipsoidal, its training is a tractable second-order cone program. The proposed method has a nice consistent statistical property. As the training size goes to infinity, the estimated normal region converges to the true provided that the magnitude of the uncertainty set decreases in a systematic way. The experimental results on three data sets clearly demonstrate its superiority over three benchmark models.

Asynchronous control of discrete-time impulsive switched systems with mode-dependent average dwell time.

This paper mainly studies the asynchronous control problem for a class of discrete-time impulsive switched systems, where "asynchronous" means the switching of the controllers has a lag to the switching of system modes. By using multiple Lyapunov functions (MLFs), the much looser asymptotic stability result of closed-loop systems is derived with a mode-dependent average dwell time (MDADT) technique. Based on the stability result obtained, the problem of asynchronous control is solved under a proper switching law. Moreover, the stability and stabilization results are formulated in form of matrix inequalities that are numerically feasible. Finally, an illustrative numerical example is presented to show the effectiveness of the obtained stability results.

The impact of cluster representatives on the convergence of the k-modes type clustering.

As a leading partitional clustering technique, k-modes is one of the most computationally efficient clustering methods for categorical data. In the k-modes, a cluster is represented by a "mode," which is composed of the attribute value that occurs most frequently in each attribute domain of the cluster, whereas, in real applications, using only one attribute value in each attribute to represent a cluster may not be adequate as it could in turn affect the accuracy of data analysis. To get rid of this deficiency, several modified clustering algorithms were developed by assigning appropriate weights to several attribute values in each attribute. Although these modified algorithms are quite effective, their convergence proofs are lacking. In this paper, we analyze their convergence property and prove that they cannot guarantee to converge under their optimization frameworks unless they degrade to the original k-modes type algorithms. Furthermore, we propose two different modified algorithms with weighted cluster prototypes to overcome the shortcomings of these existing algorithms. We rigorously derive updating formulas for the proposed algorithms and prove the convergence of the proposed algorithms. The experimental studies show that the proposed algorithms are effective and efficient for large categorical datasets.

A deterministic annealing algorithm for approximating a solution of the linearly constrained nonconvex quadratic minimization problem.

A deterministic annealing algorithm is proposed for approximating a solution of the linearly constrained nonconvex quadratic minimization problem. The algorithm is derived from applications of a Hopfield-type barrier function in dealing with box constraints and Lagrange multipliers in handling linear equality constraints, and attempts to obtain a solution of good quality by generating a minimum point of a barrier problem for a sequence of descending values of the barrier parameter. For any given value of the barrier parameter, the algorithm searches for a minimum point of the barrier problem in a feasible descent direction, which has a desired property that the box constraints are always satisfied automatically if the step length is a number between zero and one. At each iteration, the feasible descent direction is found by updating Lagrange multipliers with a globally convergent iterative procedure. For any given value of the barrier parameter, the algorithm converges to a stationary point of the barrier problem. Preliminary numerical results show that the algorithm seems effective and efficient.

A One-Layer Recurrent Neural Network for Real-Time Portfolio Optimization With Probability Criterion.

This paper presents a decision-making model described by a recurrent neural network for dynamic portfolio optimization. The portfolio-optimization problem is first converted into a constrained fractional programming problem. Since the objective function in the programming problem is not convex, the traditional optimization techniques are no longer applicable for solving this problem. Fortunately, the objective function in the fractional programming is pseudoconvex on the feasible region. It leads to a one-layer recurrent neural network modeled by means of a discontinuous dynamic system. To ensure the optimal solutions for portfolio optimization, the convergence of the proposed neural network is analyzed and proved. In fact, the neural network guarantees to get the optimal solutions for portfolio-investment advice if some mild conditions are satisfied. A numerical example with simulation results substantiates the effectiveness and illustrates the characteristics of the proposed neural network.

A deterministic annealing algorithm for the minimum concave cost network flow problem.

The existing algorithms for the minimum concave cost network flow problems mainly focus on the single-source problems. To handle both the single-source and the multiple-source problem in the same way, especially the problems with dense arcs, a deterministic annealing algorithm is proposed in this paper. The algorithm is derived from an application of the Lagrange and Hopfield-type barrier function. It consists of two major steps: one is to find a feasible descent direction by updating Lagrange multipliers with a globally convergent iterative procedure, which forms the major contribution of this paper, and the other is to generate a point in the feasible descent direction, which always automatically satisfies lower and upper bound constraints on variables provided that the step size is a number between zero and one. The algorithm is applicable to both the single-source and the multiple-source capacitated problem and is especially effective and efficient for the problems with dense arcs. Numerical results on 48 test problems show that the algorithm is effective and efficient.

A novel recurrent neural network with one neuron and finite-time convergence for k-winners-take-all operation.

In this paper, based on a one-neuron recurrent neural network, a novel k-winners-take-all ( k -WTA) network is proposed. Finite time convergence of the proposed neural network is proved using the Lyapunov method. The k-WTA operation is first converted equivalently into a linear programming problem. Then, a one-neuron recurrent neural network is proposed to get the kth or (k+1)th largest inputs of the k-WTA problem. Furthermore, a k-WTA network is designed based on the proposed neural network to perform the k-WTA operation. Compared with the existing k-WTA networks, the proposed network has simple structure and finite time convergence. In addition, simulation results on numerical examples show the effectiveness and performance of the proposed k-WTA network.

Decentralized fuzzy Hinfinity filtering for nonlinear interconnected systems with multiple time delays.

In general, due to the interaction among subsystems, it is difficult to design an Hinfinity filter for nonlinear interconnected systems. This paper introduces a decentralized Hinfinity fuzzy filter design for nonlinear interconnected systems with multiple time delays via T-S fuzzy models. The T-S fuzzy model consists of N time-delay T-S fuzzy subsystems. The decentralized Hinfinity filter is designed based on this model, which the asymptotic stability and a prescribed Hinfinity performance index are guaranteed for the overall filtering error system. A sufficient condition for the existence of such a filter is established by using linear matrix inequalities that are numerically feasible. A simulation example is given to show the effectiveness of this approach.

Ordinal pattern based similarity analysis for EEG recordings.

OBJECTIVE: Ordinal patterns analysis such as permutation entropy of the EEG series has been found to usefully track brain dynamics and has been applied to detect changes in the dynamics of EEG data. In order to further investigate hidden nonlinear dynamical characteristics in EEG data for differentiating brain states, this paper proposes a novel dissimilarity measure based on the ordinal pattern distributions of EEG series. METHODS: Given a segment of EEG series, we first map this series into a phase space, then calculate the ordinal sequences and the distribution of these ordinal patterns. Finally, the dissimilarity between two EEG series can be qualified via a simple distance measure. A neural mass model was proposed to simulate EEG data and test the performance of the dissimilarity measure based on the ordinal patterns distribution. Furthermore, this measure was then applied to analyze EEG data from 24 Genetic Absence Epilepsy Rats from Strasbourg (GAERS), with the aim of distinguishing between interictal, preictal and ictal states. RESULTS: The dissimilarity measure of a pair of EEG signals within the same group and across different groups was calculated, respectively. As expected, the dissimilarity measures during different brain states were higher than internal dissimilarity measures. When applied to the preictal detection of absence seizures, the proposed dissimilarity measure successfully detected the preictal state prior to their onset in 109 out of 168 seizures (64.9%). CONCLUSIONS: Our results showed that dissimilarity measures between EEG segments during the same brain state were significant smaller that those during different states. This suggested that the dissimilarity measure, based on the ordinal patterns in the time series, could be used to detect changes in the dynamics of EEG data. Moreover, our results suggested that ordinal patterns in the EEG might be a potential characteristic of brain dynamics. SIGNIFICANCE: This dissimilarity measure is a promising method to reveal dynamic changes in EEG, for example as occur in the transition of epileptic seizures. This method is simple and fast, so might be applied in designing an automated closed-loop seizure prevention system for absence epilepsy.

Deterministic dynamics of neural activity during absence seizures in rats.

The study of brain electrical activities in terms of deterministic nonlinear dynamics has recently received much attention. Forbidden ordinal patterns (FOP) is a recently proposed method to investigate the determinism of a dynamical system through the analysis of intrinsic ordinal properties of a nonstationary time series. The advantages of this method in comparison to others include simplicity and low complexity in computation without further model assumptions. In this paper, the FOP of the EEG series of genetic absence epilepsy rats from Strasbourg was examined to demonstrate evidence of deterministic dynamics during epileptic states. Experiments showed that the number of FOP of the EEG series grew significantly from an interictal to an ictal state via a preictal state. These findings indicated that the deterministic dynamics of neural networks increased significantly in the transition from the interictal to the ictal states and also suggested that the FOP measures of the EEG series could be considered as a predictor of absence seizures.

A deterministic annealing algorithm for approximating a solution of the min-bisection problem.

The min-bisection problem is an NP-hard combinatorial optimization problem. In this paper an equivalent linearly constrained continuous optimization problem is formulated and an algorithm is proposed for approximating its solution. The algorithm is derived from the introduction of a logarithmic-cosine barrier function, where the barrier parameter behaves as temperature in an annealing procedure and decreases from a sufficiently large positive number to zero. The algorithm searches for a better solution in a feasible descent direction, which has a desired property that lower and upper bounds are always satisfied automatically if the step length is a number between zero and one. We prove that the algorithm converges to at least a local minimum point of the problem if a local minimum point of the barrier problem is generated for a sequence of descending values of the barrier parameter with a limit of zero. Numerical results show that the algorithm is much more efficient than two of the best existing heuristic methods for the min-bisection problem, Kernighan-Lin method with multiple starting points (MSKL) and multilevel graph partitioning scheme (MLGP).

Using recurrence plot for determinism analysis of EEG recordings in genetic absence epilepsy rats.

OBJECTIVE: Understanding the transition of brain activity towards an absence seizure is a challenging task. In this paper, we use recurrence quantification analysis to indicate the deterministic dynamics of EEG series at the seizure-free, pre-seizure and seizure states in genetic absence epilepsy rats. METHODS: The determinism measure, DET, based on recurrence plot, was applied to analyse these three EEG datasets, each dataset containing 300 single-channel EEG epochs of 5-s duration. Then, statistical analysis of the DET values in each dataset was carried out to determine whether their distributions over the three groups were significantly different. Furthermore, a surrogate technique was applied to calculate the significance level of determinism measures in EEG recordings. RESULTS: The mean (+/-SD) DET of EEG was 0.177+/-0.045 in pre-seizure intervals. The DET values of pre-seizure EEG data are significantly higher than those of seizure-free intervals, 0.123+/-0.023, (P<0.01), but lower than those of seizure intervals, 0.392+/-0.110, (P<0.01). Using surrogate data methods, the significance of determinism in EEG epochs was present in 25 of 300 (8.3%), 181 of 300 (60.3%) and 289 of 300 (96.3%) in seizure-free, pre-seizure and seizure intervals, respectively. CONCLUSIONS: Results provide some first indications that EEG epochs during pre-seizure intervals exhibit a higher degree of determinism than seizure-free EEG epochs, but lower than those in seizure EEG epochs in absence epilepsy. SIGNIFICANCE: The proposed methods have the potential of detecting the transition between normal brain activity and the absence seizure state, thus opening up the possibility of intervention, whether electrical or pharmacological, to prevent the oncoming seizure.

Neural networks for nonlinear and mixed complementarity problems and their applications.

This paper presents two feedback neural networks for solving a nonlinear and mixed complementarity problem. The first feedback neural network is designed to solve the strictly monotone problem. This one has no parameter and possesses a very simple structure for implementation in hardware. Based on a new idea, the second feedback neural network for solving the monotone problem is constructed by using the first one as a subnetwork. This feedback neural network has the least number of state variables. The stability of a solution of the problem is proved. When the problem is strictly monotone, the unique solution is uniformly and asymptotically stable in the large. When the problem has many solutions, it is guaranteed that, for any initial point, the trajectory of the network does converge to an exact solution of the problem. Feasibility and efficiency of the proposed neural networks are supported by simulation experiments. Moreover, the feedback neural network can also be applied to solve general nonlinear convex programming and nonlinear monotone variational inequalities problems with convex constraints.